package xyz.sekai52799.utils;

import java.util.ArrayList;
import java.util.List;

/**
 * 全排列，输出二维数组
 */
public class FullPermutation {

    private int n;
    public FullPermutation(){}

    public FullPermutation(int n){
        this.n = n;
    }

    public List<int[]> getFullPermutation() {
        List<int[]> result = new ArrayList<>();

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
        }
        permute(result, nums, 0, n-1);
        return result;
    }

    private void permute(List<int[]> result, int[] nums, int l, int r) {
        if (l == r) {
            int[] tempNums = new int[nums.length];
            System.arraycopy(nums, 0, tempNums, 0, nums.length);
            result.add(tempNums);
            return;
        }
        for (int i = l; i <= r; i++) {
            // 将i位置的元素与l位置的元素交换
            swap(nums, l, i);
            // 递归调用permute来固定l位置，对l+1到r位置的元素进行排列
            permute(result, nums, l + 1, r);
            // 递归完成后需要将元素换回原来的位置，以便进行下一次循环
            swap(nums, l, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
